package nowcoder;

import java.util.LinkedList;

public class ConvertBST {

	public TreeNode convert(TreeNode pRootOfTree) {
		if(pRootOfTree == null)
			return null;
		
		TreeNode current = pRootOfTree;
		LinkedList<TreeNode> list = new LinkedList<>();
		LinkedList<TreeNode> stack = new LinkedList<>();
		
		while(current != null || !stack.isEmpty()) {
			while(current != null) {
				stack.push(current);
				current = current.left;
			}
			
			if(!stack.isEmpty()) {
				current = stack.pop();
				list.add(current);
				current = current.right;
			}
		}
		
		TreeNode newRoot = list.get(0);
		newRoot.left = null;
		newRoot.right = null;
		TreeNode currentNode = newRoot, nextNode;
		for(int i = 1; i < list.size(); i++) {
			nextNode = list.get(i);
			currentNode.right = nextNode;
			nextNode.left = currentNode;
			currentNode = nextNode;
		}
		
		return newRoot;
		
	}

}
